package com.asia.algorithmcode.dynamicProgram;

import java.util.Arrays;

/**
 * @DESCRIPTION:
 * @USER: wanfu
 * @DATE: 2025/5/14 星期三 13:43
 */
public class NumDistinct {

    public static void main(String[] args) {
        String s = "rabbbit", t = "rabbit";

        System.out.println(new NumDistinct().numDistinct(s, t));
    }

    public int numDistinct(String s, String t) {
        int m = s.length();
        int n = t.length();

        s = " " + s;
        t = " " + t;

        long[][] dp = new long[m + 1][n + 1];

        for (int i = 0; i <= m; i++) {
            dp[i][0] = 1;
        }

        // 在s的前i个字符中，t字符串出现的次数
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (j > i) {
                    continue;
                }
                dp[i][j] = dp[i - 1][j]; //  不选用i
                if (s.charAt(i) == t.charAt(j)) {
                    dp[i][j] += dp[i - 1][j - 1]; // 选用i
                }
            }
        }
        return (int)dp[m][n];
    }
}
